import java.util.*;

public class Main {
    public static void main(String[] args) {
        List<List<String>> tickets1 = Arrays.asList(
                Arrays.asList("MUC","LHR"),
                Arrays.asList("JFK","MUC"),
                Arrays.asList("SFO","SJC"),
                Arrays.asList("LHR","SFO")
        );
        List<List<String>> tickets2 = Arrays.asList(
                Arrays.asList("JFK","SFO"),
                Arrays.asList("JFK","ATL"),
                Arrays.asList("SFO","ATL"),
                Arrays.asList("ATL","JFK"),
                Arrays.asList("ATL","SFO")
        );
        System.out.println(new Solution1().findItinerary(tickets1));
        System.out.println(new Solution1().findItinerary(tickets2));
    }
}

class Solution {

    final String startCity = "JFK";

    int[][] graph;
    String[] cities;
    Map<String, Integer> city2idx;

    public List<String> findItinerary(List<List<String>> tickets) {
        makeGraph(tickets);
        List<String> ans = new ArrayList<>();
        ans.add(startCity);
        int startCityIdx = city2idx.get(startCity);
        backtracking(ans, startCityIdx, 0, tickets.size());
        return ans;
    }

    boolean backtracking(List<String> ans, int curCity, int curCount, int ticketNum) {
        if (curCount == ticketNum) {
            return true;
        }

        for (int i = 0; i < graph.length; i++) {
            if (graph[curCity][i] > 0) {
                graph[curCity][i]--;
                ans.add(cities[i]);
                boolean flag = backtracking(ans, i, curCount + 1, ticketNum);
                if (flag) {
                    return true;
                }
                ans.remove(ans.size() - 1);
                graph[curCity][i]++;
            }
        }
        return false;
    }

    void makeGraph(List<List<String>> tickets) {
        SortedSet<String> citySet = new TreeSet<>();
        for (List<String> each : tickets) {
            citySet.add(each.get(0));
            citySet.add(each.get(1));
        }

        //make city2idx
        Iterator<String> it = citySet.iterator();
        cities = new String[citySet.size()];
        for (int i = 0; i < citySet.size(); i++) {
            cities[i] = it.next();
        }
        city2idx = new HashMap<>();
        for (int i = 0; i < cities.length; i++) {
            city2idx.put(cities[i], i);
        }

        //make graph
        graph = new int[citySet.size()][citySet.size()];
        for (List<String> each : tickets) {
            graph[city2idx.get(each.get(0))][city2idx.get(each.get(1))]++;
        }
    }
}

//Hierholzer算法
class Solution1 {

    final String startCity = "JFK";

    Map<String, PriorityQueue<String>> graph = new HashMap<>();

    public List<String> findItinerary(List<List<String>> tickets) {
        makeGraph(tickets);
        Deque<String> ans = new ArrayDeque<>();
        dfs(ans, startCity);
        return new ArrayList<>(ans);
    }

    void makeGraph(List<List<String>> tickets) {
        for (List<String> ticket : tickets) {
            String src = ticket.get(0), dist = ticket.get(1);
            if (!graph.containsKey(src)) {
                graph.put(src, new PriorityQueue<>());
            }
            graph.get(src).offer(dist);
        }
    }

    void dfs(Deque<String> ans, String curCity) {
        PriorityQueue<String> dests = graph.get(curCity);
        while (dests != null && !dests.isEmpty()) {
            dfs(ans, dests.poll());
        }
        ans.push(curCity);
    }
}